package datastructure.graph.最小生成树;


import datastructure.tree.IndexMinPQ;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/28 10:26 上午
 */
public class PrimMST {
    private Edge[] edgeTo;
    private double[] distTo;
    private boolean[] marked;

    private double weight=0.0;
    private IndexMinPQ<Double> pq;

    public PrimMST(EdgeWeightedGraph graph) {
        edgeTo=new Edge[graph.E()];
        distTo=new double[graph.V()];
        marked=new boolean[graph.V()];
        pq=new IndexMinPQ<Double>(graph.V());

        for (int i = 0; i < graph.V(); i++) {
            distTo[i]=Double.MAX_VALUE;
        }
        for (int i = 0; i < graph.V(); i++) {
            if (!marked[i]){
                prim(graph,i);
            }
        }
    }

    private void prim(EdgeWeightedGraph graph, int v) {
        distTo[v]=0.0;
       pq.insert(v,distTo[v]);
       while (!pq.isEmpty()){
           int w = pq.delMin();
           visit(graph,w);
       }
    }

    private void visit(EdgeWeightedGraph graph, int v) {
        marked[v]=true;
        weight+=distTo[v];
        for (Edge edge : graph.adj(v)) {
            int other = edge.other(v);
            if (marked[other]){
                continue;
            }
            if (edge.weight()<distTo[other]){
                edgeTo[other]=edge;
                distTo[other]=edge.weight();
                if (pq.contains(other)){
                    pq.changeKey(other,distTo[other]);
                }else {
                    pq.insert(other,distTo[other]);
                }
            }
        }
    }
    public Iterable<Edge> edges(){
        Queue<Edge> mst = new LinkedList<Edge>();
        for (int v = 0; v < edgeTo.length; v++) {
            Edge e = edgeTo[v];
            if (e != null) {
                mst.add(e);
            }
        }
        return mst;
    }
    public double weight(){
        return weight;
    }

    public static void main(String[] args) {

        EdgeWeightedGraph graph= new EdgeWeightedGraph(8);
        graph.addEdge(new Edge(4,5,0.35));
        graph.addEdge(new Edge(4,7,0.37));
        graph.addEdge(new Edge(5,7,0.28));
        graph.addEdge(new Edge(0,7,0.16));
        graph.addEdge(new Edge(1,5,0.32));
        graph.addEdge(new Edge(0,4,0.38));
        graph.addEdge(new Edge(2,3,0.17));
        graph.addEdge(new Edge(1,7,0.19));
        graph.addEdge(new Edge(0,2,0.26));
        graph.addEdge(new Edge(1,2,0.36));
        graph.addEdge(new Edge(1,3,0.29));
        graph.addEdge(new Edge(2,7,0.34));
        graph.addEdge(new Edge(6,2,0.40));
        graph.addEdge(new Edge(3,6,0.52));
        graph.addEdge(new Edge(6,0,0.58));
        graph.addEdge(new Edge(6,4,0.93));
        PrimMST mst = new PrimMST(graph);
        for (Edge e : mst.edges()) {
            System.out.println(e);
        }
        System.out.println(mst.weight());
    }
}
